Queries

Memory limit: 32 MB

Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has already found out that whilst deciphering a message he will have to answer multiple queries of the form "for given integers , and , find the number of integer pairs satisfying the following conditions:

• ,
• ,
• , where is the greatest common divisor of and ".

Task

Write a programme which:

• reads from the standard input a list of queries, which the Byteasar has to give answer to,
• calculates answers to the queries,
• writes the outcome to the standard output.

Input

The first line of the standard input contains one integer (), denoting the number of queries. The following lines contain three integers each: , and (), separated by single spaces. Each triplet denotes a single query.

Output

Your programme should write lines to the standard output. The 'th line should contain a single integer: the answer to the 'th query from the standard input.

Example

For the input data:

2
4 5 2
6 4 3

the correct result is:

3
2

The pairs satisfying the first query are: , and . The pairs satisfying the second query are: and .

Task author: Jakub Radoszewski.